package code.oldCode.feishuSpecializedTraining.list;

import utils.ListNode;

import java.util.HashMap;

public class MyList2 {
    // 19. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode headPre = new ListNode();
        headPre.next = head;
        ListNode p = headPre;
        ListNode q = headPre;
        int count = 0;
        while (p.next != null) {
            p = p.next;
            count++;
            if (count > n) {
                q = q.next;
            }
        }
        // 删除（跳过）
        q.next = q.next.next; // 题目的测试数据范围 & p 保证不会出现q.next == null
        // 如果删的是第一个节点
        if (q == headPre) {
            head = q.next;
        }
        return head;
    }

    // 面试题 02.07. 链表相交
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

    // 142. 环形链表 II
    public ListNode detectCycle(ListNode head) {
        // 空间O(n) hashMap
        HashMap<ListNode, Integer> hashMap = new HashMap<>();
        ListNode node = head;
        int pos = 0;
        while (node != null) {
            if (hashMap.containsKey(node)) {
                return node;
            }
            hashMap.put(node, pos);
            pos++;
            node = node.next;
        }
        return null;
    }
    public ListNode detectCycle_(ListNode head) {
        // 空间O(1) 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 相交后
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        MyList2 myList2 = new MyList2();
    }
}
